# -*- coding: utf-8 -*-
################################################################################
#
# Copyright (c) 2014 Baidu.com, Inc. All Rights Reserved
#
################################################################################
"""
保存已抓取的url列表，用于去重。用布隆过滤器思想，且利用了python模块之天然单例特性。

要使用的时候 from url_table import url_bloom_filter

然后 url_bloom_filter.set(添加url)

url_bloom_filter.test(检测url)，url存在则返回True，不在返回False

Authors: caopeirui(caopeirui@baidu.com)
Date:	2018/04/19 20:10:41
"""
import random
import array

class BitMap(object):
    BITMASK= [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80]
    BIT_CNT = [bin(i).count("1") for i in range(256)]

    def __init__(self, maxnum=0):
        """
        Create a BitMap
        """
        nbytes = int((maxnum + 7) / 8)
        self.bitmap = array.array('B', [0 for i in range(nbytes)])

    def set(self, pos):
        """
        Set the value of bit@pos to 1
        """
        self.bitmap[int(pos / 8)] |= self.BITMASK[pos % 8]

    def test(self, pos):
        """
        Return bit value
        """
        return (self.bitmap[int(pos / 8)] & self.BITMASK[pos % 8]) != 0

class BloomFilter:
    def __init__(self, mapsize=160000, max_node_size=10000, random_num=8):
        '''
        Args:
            mapsize 为bitmap的size
            max_node_size 为最大容纳的数据个数
            random_num 生成随机数个数，这里使用伪随机数来代替hash函数。
        '''
        self.m = mapsize
        self.n = max_node_size
        self.k = random_num
        self.bitmap = BitMap(maxnum=self.m)
        self.count = 0

    def set(self, string):
        '''将输入的数据存入到布隆过滤器
        '''
        calcmap = self.calcMap(string)
        for x in calcmap:
            self.bitmap.set(x)

    def test(self, string):
        '''测试输入的数据是否在布隆过滤器中
        在则返回True，不在返回False
        '''
        calcmap = self.calcMap(string)
        for x in calcmap:
            if not self.bitmap.test(x):
                return False
        return True

    def calcMap(self, string):
        '''计算输入的数据映射到bitmap的位置
        '''
        r = random.Random(string)
        lv1random = [r.random() for x in range(self.k)]
        return [int(random.Random(x).random()*self.m) for x in lv1random]

url_bloom_filter = BloomFilter()

if __name__ == '__main__':
    url_bloom_filter.set('http://www.test.com')
    url_bloom_filter.set('http://www.abc.com')

    print(url_bloom_filter.test('http://www.test1.com'))
    print(url_bloom_filter.test('http://www.abc.com'))
    print(url_bloom_filter.test('http://www.abc.comm'))